package algorithm_demo.demo01;

/**
 * 二分查找
 * 查找
 * <p>
 * 二分法
 * 1. 有序数组中找到num
 * 2. 有序数组中找到>=num最左的位置
 * 3. 有序数组中找到<=num最右的位置
 * 4. 局部最小值问题
 *
 * @author Api
 * @date 2023/1/27 1:45
 */
public class Code14_BinarySearch {
    //4.局部最小值问题
    //arr无序，arr相邻的数不相等
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {//如果第一个数小于第二个数时，局部最小返回一个可以为arr[0]
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {//如果最后一个数小于倒数第二个数时，局部最小返回一个可以为arr[N-1]
            return N - 1;
        }
        int L = 0;
        int R = N - 1;
        //L...R肯定有局部最小
        while (L < R - 1) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;//出现类似两个数时，比如下标0和1做比较时，则为不能为-1.
    }
}
